package com.it.data_tree.tree.redBlackTree;

import static com.it.data_tree.tree.redBlackTree.Color.BLACK;
import static com.it.data_tree.tree.redBlackTree.Color.RED;

/**
 * @Author: Coke
 * @DateTime: 2023/05/01/21:22
 * @注释: TODO
 **/
public class RedBlackTree {
    
    public RedBlackNode root;
    
    /**
     * @param node:
     * @return boolean
     * @作者: Coke
     * @注释: 判断节点是否为红色
     * @DateTime: 2023/5/1 22:13
     */
    public boolean isRed (RedBlackNode node) {
        return node != null && node.color == RED;
    }
    
    /**
     * @param node:
     * @return boolean
     * @作者: Coke
     * @注释: 判断节点是否为黑色
     * @DateTime: 2023/5/1 22:13
     */
    public boolean isBlack (RedBlackNode node) {
        return node == null || node.color == BLACK;
    }
    
    /**
     * @param pink: 需要右旋的根节点
     * @return void
     * @作者: Coke
     * @注释: 右旋操作
     * @DateTime: 2023/5/2 15:41
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public void rightRotate (RedBlackNode pink) {
        // 1. 获取旋转节点的父节点
        RedBlackNode parent = pink.parent;
        // 2. 获取到旋转节点的左子节点
        RedBlackNode yellow = pink.left;
        // 3. 获取左子节点的右子节点
        RedBlackNode green = yellow.right;
        // 4. 如果不为空 改变父节点
        if (green != null) {
            green.parent = pink;
        }
        // 5. 将左子节点的右节点设为旋转节点
        yellow.right = pink;
        
        yellow.parent = parent;
        // 6. 将旋转节点的右节点设为 左子节点的右节点
        pink.left = green;
        // 7. 如果为空 当前节点为根节点（情况一）
        if (parent == null) {
            root = yellow;
            // 8. 不为空判断在根节点的左边还是右边（情况二）
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
        pink.parent = yellow;
    }
    
    /**
     * @param pink: 需要左旋的根节点
     * @return void
     * @作者: Coke
     * @注释: 左旋操作
     * @DateTime: 2023/5/2 16:16
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public void leftRotate (RedBlackNode pink) {
        // 1. 获取旋转节点的父节点
        RedBlackNode parent = pink.parent;
        // 2. 获取到旋转节点的右子节点
        RedBlackNode yellow = pink.right;
        // 3. 获取右子节点的左子节点
        RedBlackNode green = yellow.left;
        // 4. 如果不为空 改变父节点
        if (green != null) {
            green.parent = pink;
        }
        // 5. 将右子节点的子节点设为旋转节点
        yellow.left = pink;
        
        yellow.parent = parent;
        // 6. 将旋转节点的左节点设为 右子节点的左节点
        pink.right = green;
        // 7. 如果为空 当前节点为根节点（情况一）
        if (parent == null) {
            root = yellow;
            // 8. 不为空判断在根节点的左边还是右边（情况二）
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
       pink.parent = yellow;
    }
    
    /**
     * @param key:   建
     * @param value: 值
     * @return void
     * @作者: Coke
     * @注释: 新增或者更新（正常增、遇到红红不平衡进行调整）
     * @DateTime: 2023/5/2 16:19
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public void put (int key, Object value) {
        RedBlackNode node = root;
        RedBlackNode parent = null;
        while (node != null) {
            parent = node;
            // 向左找
            if (key < node.key) {
                node = node.left;
                // 向右找
            } else if (key > node.key) {
                node = node.right;
                // 找到了 更新
            } else {
                node.value = value;
                return;
            }
        }
        // 创建新增的节点
        RedBlackNode newNode = new RedBlackNode(key, value);
        if (parent == null) {
            root = newNode;
            // 新增节点在左边 (并设置新增节点的父节点)
        } else if (key < parent.key) {
            parent.left = newNode;
            newNode.parent = parent;
            // 新增节点在右边 (并设置新增节点的父节点)
        } else {
            parent.right = newNode;
            newNode.parent = parent;
        }
        fixRedRed(newNode);
    }
    
    /**
     * @param newNode: 需要平衡的节点（新增的节点）
     * @return void
     * @作者: Coke
     * @注释: 调整平衡（两个红色节点相邻时）
     * @DateTime: 2023/5/2 19:41
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public void fixRedRed (RedBlackNode newNode) {
        // 1. 如果新增的节点为根节点，将根节点变为黑色
        if (root == newNode) {
            newNode.color = BLACK;
            return;
        }
        // 2. 新增节点的父节点为黑色，则无需调整
        if (isBlack(newNode.parent)) {
            return;
        }
        // 3. 新增节点的父节点为红色（叔叔节点也为红色）
        RedBlackNode parent = newNode.parent;
        RedBlackNode uncle = newNode.uncle();
        RedBlackNode grandParent = parent.parent;
        if (isRed(uncle)) {
            parent.color = BLACK;
            uncle.color = BLACK;
            grandParent.color = RED;
            fixRedRed(grandParent);
            return;
        }
        // 4. 新增节点的父节点为红色（叔叔节点为黑色）
        // 4.1 父亲为左孩子，插入节点也是左孩子，此时为LL不平衡
        if (parent.isLeftChild() && newNode.isLeftChild()) {
            parent.color = BLACK;
            grandParent.color = RED;
            rightRotate(grandParent);
            // 4.2 父亲为左孩子，插入节点是右孩子，此时为LR不平衡
        } else if (parent.isLeftChild() && ! newNode.isLeftChild()) {
            leftRotate(parent);
            newNode.color = BLACK;
            grandParent.color = RED;
            rightRotate(grandParent);
            // 4.3 父亲为右孩子，插入节点也是右孩子，此时为RR不平衡
        } else if (! parent.isLeftChild() && ! newNode.isLeftChild()) {
            parent.color = BLACK;
            grandParent.color = RED;
            leftRotate(grandParent);
            // 4.4 父亲为右孩子，插入节点是左孩子，此时为RL不平衡
        } else {
            rightRotate(parent);
            newNode.color = BLACK;
            grandParent.color = RED;
            leftRotate(grandParent);
        }
    }
    
    /**
     * @param key: 查找的值
     * @return RedBlackNode 查找的节点
     * @作者: Coke
     * @注释: 查找某个节点
     * @DateTime: 2023/5/3 13:26
     */
    public RedBlackNode find (int key) {
        RedBlackNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }
    
    /**
     * @param delete: 要删除的节点
     * @return RedBlackNode 删除后剩下的节点
     * @作者: Coke
     * @注释: 查找删除后剩下的节点
     * @DateTime: 2023/5/3 13:35
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public RedBlackNode findReplace (RedBlackNode delete) {
        // 1. 两个子节点都是null （叶子节点） 删除后返回null
        if (delete.left == null && delete.right == null) {
            return null;
        }
        // 2. 只有左子节点
        if (delete.right == null) {
            return delete.left;
        }
        // 3. 只有右子节点
        if (delete.left == null) {
            return delete.right;
        }
        // 4. 有两个子节点（返回后继节点）
        RedBlackNode min = delete.right;
        while (min.left != null) {
            min = min.left;
        }
        return min;
    }
    
    /**
     * @param key: 删除节点的key
     * @return void
     * @作者: Coke
     * @注释: 删除某个节点
     * @DateTime: 2023/5/3 14:09
     */
    // https://boardmix.cn/app/share/CAE.CK-J_gsgASoQaEmZGKxuLwWK9zawupIcMDAGQAE/z7vil3， 点击链接加入boardmix中的文件「红黑树」
    public void remove (int key) {
        // 1. 查找删除的节点
        RedBlackNode deleted = find(key);
        // 2. 删除节点不存在直接返回
        if (deleted == null) {
            return;
        }
        // 3. 执行删除方法
        doRemove(deleted);
    }
    
    /**
     * @param deleted: 需要删除的节点
     * @return void
     * @作者: Coke
     * @注释: 执行删除方法的逻辑（用到了李代桃僵技巧、遇到黑黑不平衡进行调整）
     * @DateTime: 2023/5/3 14:12
     */
    
    private void doRemove (RedBlackNode deleted) {
        RedBlackNode parent = deleted.parent;
        // 1. 找到删除后的元素
        RedBlackNode replace = findReplace(deleted);
        // 2. 删除节点没有孩子
        if (replace == null) {
            // 2.1 删除节点为根节点
            if (deleted == root) {
                root = null;
                // 2.2 删除的不是根节点
            } else {
                
                // 如果删除的叶子节点是黑色
                if (isBlack(deleted)) {
                    // 需要双黑平衡处理
                    fixDoubleBlack(deleted);
                } else {
                    // 无需平衡处理
                }
                
                // 如果删除的是左孩子
                if (deleted.isLeftChild()) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                // 维护父节点的指向
                deleted.parent = null;
            }
            return;
        }
        // 3. 删除节点有一个孩子
        if (deleted.left == null || deleted.right == null) {
            // 3.1 删除节点为根节点
            if (deleted == root) {
                root.key = replace.key;
                root.value = replace.value;
                root.left = root.right = null;
                // 3.2 删除的不是根节点
            } else {
                // 如果删除的是左孩子
                if (deleted.isLeftChild()) {
                    parent.left = replace;
                } else {
                    parent.right = replace;
                }
                // 维护父节点的指向
                replace.parent = parent;
                // 将删除节点的 左 右 父 都置为null
                deleted.left = deleted.right = deleted.parent = null;
                
                // 如果删除的是黑色 并且 剩下的也是黑色
                if (isBlack(deleted) && isBlack(replace)) {
                    // 需要双黑平衡处理
                    fixDoubleBlack(replace);
                } else {
                    // 只需要将剩下的红色节点变成黑色
                    replace.color = BLACK;
                }
            }
            return;
        }
        
        // 4. 删除节点有两个孩子 ==> 经过以下操作将有两个孩子的节点抓换成了 有一个孩子 或者 没有孩子
        // 4.1 交换删除节点与后继节点的key
        int k = deleted.key;
        deleted.key = replace.key;
        replace.key = k;
        // 4.2 交换删除节点与后继节点的值
        Object v = deleted.value;
        deleted.value = replace.value;
        replace.value = v;
        doRemove(replace);
    }
    
    /**
     * @param x: 需要平衡的节点
     * @return void
     * @作者: Coke
     * @注释: 双黑平衡处理 （删除节点和剩下节点都是黑色）
     * @DateTime: 2023/5/3 16:06
     */
    private void fixDoubleBlack (RedBlackNode x) {
        // 1. 如果已经是根节点 无需在调整了
        if (x == root) {
            return;
        }
        // 分别获取父节点和兄弟节点（方便后面使用）
        RedBlackNode parent = x.parent;
        RedBlackNode sibling = x.sibling();
        // 2. 情况三：兄弟节点是红色
        if (isRed(sibling)) {
            // 2.1  判断 x 节点在左边还是右边 决定旋转方向
            if (x.isLeftChild()) {
                leftRotate(parent);
            } else {
                rightRotate(parent);
            }
            // 2.2 改变父节点和原来的兄弟节点颜色
            parent.color = RED;
            sibling.color = BLACK;
            // 2.3 进行递归调用 触发情况四 或 五
            fixDoubleBlack(x);
        }
        // 判断兄弟节点是否为空
        if (sibling != null) {
            // 3. 兄弟是黑色（判断左右两个侄子是否都是黑色）
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                sibling.color = RED;
                // 如果父节点是红色
                if (isRed(parent)) {
                    parent.color = BLACK;
                } else {
                    fixDoubleBlack(parent);
                }
                // 4. 兄弟是黑色，侄子至少有一个是黑色
            } else {
                // 4.1 LL不平衡 （兄弟是左孩子，左侄子是红色）
                if (sibling.isLeftChild() && isRed(sibling.left)) {
                    rightRotate(parent);
                    sibling.left.color = BLACK;
                    sibling.color = parent.color;
                    // 4.2 LR不平衡（兄弟是左孩子，右侄子是红色）
                } else if (sibling.isLeftChild() && isRed(sibling.right)) {
                    sibling.right.color = parent.color;
                    leftRotate(sibling);
                    rightRotate(parent);
                    // 4.3 RR不平衡（兄弟是右孩子，右侄子是红色）
                } else if (! sibling.isLeftChild() && isRed(sibling.right)) {
                    leftRotate(parent);
                    sibling.right.color = BLACK;
                    sibling.color = parent.color;
                    // 4.4 RL不平衡 （兄弟是右孩子，左侄子是红色）
                } else {
                    sibling.left.color = parent.color;
                    rightRotate(sibling);
                    leftRotate(parent);
                }
                parent.color = BLACK;
            }
        } else {
            fixDoubleBlack(parent);
        }
    }
}
